package leetcode_901_1000;

import java.util.Arrays;
import java.util.Map;

public class LeeCode_1000_failed {
    public static void main(String[] args) {
        System.out.println(mergeStones(new int[]{3, 2, 4, 1}, 2));
        System.out.println(mergeStones(new int[]{3, 2, 4, 1}, 3));
        System.out.println(mergeStones(new int[]{3, 5,1,2,6}, 3));
    }
    private static int mergeStones(int[] stones, int k) {
        if ((stones.length - 1) % (k - 1) != 0){
            return -1;
        }
        int[] minI = new int[2];
        int ans = 0;

        int[] arr = stones;
        while (arr.length != 1) {
            int minN = Integer.MAX_VALUE;
            for (int i = 0; i <= arr.length - k; i++) {
                int sum = 0;
                for (int j = i; j < i + k; j++) {
                    sum += arr[j];
                }
                if (minN > sum){
                    minN = sum;
                    minI[0] = i;
                    minI[1] = i + k - 1;
                }
            }
            ans += minN;
            int[] arrN = new int[arr.length - (k - 1)];
            for (int i = 0; i < minI[0]; i++) {
                arrN[i] = arr[i];
            }
            arrN[minI[0]] = minN;
            for (int i = arr.length - 1; i > minI[1]; i--){
                arrN[i - (k - 1)] = arr[i];
            }
            arr = arrN;
        }
        return ans;
    }
}
